package cc.wsyw126.java.nowcoder.interview;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by Administrator on 2017/4/26.
 * 请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
 * 给定一个int[] numbers(C++中为vector&ltint>)，其中第一个元素为栈顶，请返回排序后的栈。
 * 请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。
 */
public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        return doTask(numbers);
    }

    private ArrayList<Integer> doTask(int[] numbers) {
        Stack<Integer> stack = new Stack<>();
        stack.push(numbers[0]);
        for (int i = 1; i < numbers.length; i++) {
            int position = i;
            Integer peek = stack.peek();
            while (peek < numbers[i]) {
                numbers[--position] = stack.pop();
                if (!stack.isEmpty()) {
                    peek = stack.peek();
                }else {
                    break;
                }
            }
            stack.push(numbers[i]);
            for (int j = position; j < i; j++) {
                stack.push(numbers[j]);
            }
        }
        ArrayList<Integer> integers = new ArrayList<>(numbers.length);
        for (int i = numbers.length - 1; i >= 0; i--) {
            Integer pop = stack.pop();
            numbers[i] = pop;
        }
        for (int i = 0; i < numbers.length; i++) {
            integers.add(numbers[i]);
        }
        return integers;
    }

    public static void main(String[] args) {
        TwoStacks twoStacks = new TwoStacks();
        ArrayList<Integer> integers = twoStacks.twoStacksSort(new int[]{1,2,3});
        for (int i = 0; i < integers.size(); i++) {
            System.out.print(integers.get(i) + "\t");
        }

    }
}
